/**************************************************************************************
*
*	Copyright (C) 2009 - 2012 Brent Andrew O. Chua - See LICENSE.txt for more info.
*		
*	Filename	-	LockFreeQueue.cpp
*
*	Comments	-	See LockFreeQueue.h
*
**************************************************************************************/
#include "Math.h"

namespace Pulse
{
	template < typename T >
	PSX_INLINE LockFreeQueue<T>::LockFreeQueue( void )
		: m_size( 0 ), m_pBuffer( PSX_NULL )
	{

	}

	template < typename T >
	PSX_INLINE LockFreeQueue<T>::LockFreeQueue( SIZE_T size )
	{
		Initialize( size );
	}

	template < typename T >
	PSX_INLINE LockFreeQueue<T>::~LockFreeQueue( void )
	{
		Cleanup();
	}

	template < typename T >
	PSX_INLINE BOOL LockFreeQueue<T>::Enqueue( T &elem )
	{
		Node currNode( 0, PSX_NULL );
		Node newNode( 0, elem );

		while ( (m_writeIndex - m_readIndex) < m_size )
		{
			const INT writeKey = m_writeIndex;
			const INT writeBucket = m_writeIndex & m_bucketMask;

			currNode.key = writeKey;
			newNode.key = writeKey;

			if ( Atomic::CompareExchange( &m_pBuffer[writeBucket].value, newNode.value, currNode.value ) == currNode.value )
			{
				++m_writeIndex;
				return TRUE;
			}
		}

		return FALSE;
	}

	template < typename T >
	PSX_INLINE T & LockFreeQueue<T>::Dequeue( void )
	{
		while ( m_readIndex != m_writeIndex )
		{
			const INT readKey = m_readIndex;
			const INT readBucket = m_readIndex & m_bucketMask;
			Node currNode( readKey, m_pBuffer[readBucket].pElem );

			if ( currNode.pElem )
			{
				Node newNode( readKey + m_size, PSX_NULL );

				if ( Atomic::CompareExchange( &m_pBuffer[readBucket].value, newNode.value, currNode.value ) == currNode.value )
				{
					++m_readIndex;
					return currNode.pElem;
				}
			}
		}

		return PSX_NULL;
	}

	template < typename T >
	PSX_INLINE void LockFreeQueue<T>::Initialize( SIZE_T size )
	{
		Cleanup();

		m_size = Math::NearestPowerOfTwo( size );
		m_bucketMask = m_size - 1;

		// NOTE: Add 128 for the size of cache line. The size of the 
		//	cache line should be figured out at run-time. Different platforms
		//	have different cache line sizes.
		m_pBuffer = PSX_MallocAligned( PSX_SizeOf( Node ) * size, 128 );
		PSX_Assert( m_pBuffer, "Failed to allocate memory." );

		for ( UINT i = 0; i < size; ++i )
		{
			m_pBuffer[i].key = i;
			m_pBuffer[i].pElem = PSX_NULL;
		}
	}

	template < typename T >
	void LockFreeQueue<T>::Cleanup( void )
	{
		if ( m_pBuffer )
		{
			PSX_DeallocAligned( m_pBuffer );
			m_pBuffer = PSX_NULL;
		}
	}


}